class Solution {
public:
    /*
    判断一个序列是否是二叉排序树的后续遍历
    已知：1、二叉排序树的左子树都小于跟结点，右子树都大于跟结点
        2、后序遍历的最后一个结点是根节点
     找到二叉树右子树部分，判断二叉树的所有右子树是否大于根节点，如果小于说明false
    */
    vector<int>seq;
    bool VerifySquenceOfBST(vector<int> sequence) {
        seq=sequence;
        if(seq.empty())
            return false;
        return dfs(0,seq.size()-1);
    }
    bool dfs(int low,int high)
    {
        if(low>=high)
            return true;
        int father=seq[high];  
        int i,k;
        k=low;
        while(k<high&&seq[k]<father) k++;
        //k指向右子树开始结点
        for(i=k;i<high;i++)
        {
            if(seq[i]<father) //右子树的所有原始应该比父节点大
                return false;
        }
        return dfs(low,k-1)&&dfs(k,high-1);
        
    }
};